The present invention is directed to resource arbitration for hardware systems. More particularly, the present invention is directed to resource arbitration using round robin priority selection logic.
In hardware systems, e.g., computer systems, it is often advantageous to use a round robin scheme for resolving conflicts in priority queues. U.S. Pat. No. 5,377,332 to Entwistle et al. shows an apparatus for arbitrating the use of a system bus that includes such a round robin scheme. The round robin scheme gives a reasonably "fair" treatment of all process requests in the queue. In such systems, the round robin priority token is updated when a process request is granted priority to the queue.
FIG. 1 illustrates operation of round robin priority logic in accordance with the prior art. In cycle 0, Process P1 (Task 1) is selected busying Resource A in cycles 2 and 3. The priority token is then updated to point to P1.
In cycle 1, Process Pr (Task 2) is selected, is found to have a conflict with Resource A in cycle 2, and is therefore rejected. The priority token is updated to point to Pr.
In cycle 2, Process Pn (Task 3) is selected and no conflict is found for Resource B in cycle 3. The priority token is updated to point to Pn.
In cycle 3, Process P2 (Task 4) is selected and, as no conflict is found for Resource A in cycle 4, Resource A is busied in cycles 5 and 6. The priority token is then updated to point to P2.
In cycle 4, Process Pr (Task 2) is selected, is found to have a conflict with Resource A in cycle 5, and is therefore rejected. The priority token is updated to point to Pr.
In cycle 5, Process Pn (Task 5) is selected and no conflict is found for Resource B in cycle 6. The priority token is updated to point to Pn.
In cycle 6, Process P2 (Task 6) is selected and, as no conflict is found for Resource A in cycle 7, Resource A is busied in cycles 8 and 9. The priority token is updated to point to P2.
In cycle 7, Process Pr (Task 2) is selected, is found to have a conflict with Resource A in cycle 8, and is therefore rejected. The priority token is updated to point to Pr.
In cycle 8, Process Pn (Task 7) is selected and no conflict is found for Resource B in cycle 9. The priority token is updated to point to Pn.
It may be appreciated that there are times when allowing a particular process request into the queue will have an adverse affect on system performance. For example, a resource that is needed by a particular process may be tied up and allowing that process request to proceed might cause future rejects or system hangs. In FIG. 1, this is illustrated by Task 2, which keeps getting rejected. This reject causes resources A and B to have periodic idle cycles.
Accordingly, there is a need in the art for a method and apparatus for resource arbitration that insures the availability of requested resources prior to granting priority to a process request. Additionally, there is a need in the art for a method and apparatus for resource arbitration that insures that a process is not continually preempted due to a resource conflict resulting in an indefinite lockout of the process request.